package a10_动态规划;

import java.util.Arrays;

/**
 * <p>
 * a13_分割等和子集
 * </p>
 *
 * @author flyduck
 * @since 2025/2/11
 */
public class a13_分割等和子集 {
    public static void main(String[] args) {
        boolean b = canPartition(new int[]{2, 2, 1, 1});
        System.out.println();
    }
    //比如集合总和为22，我们只要能促成和为11的集合就可以
    //抽象成背包问题，就是装满容量为11背包
    //因为每个物品只能放置一次，所以是01背包
    public static boolean canPartition(int[] nums) {
        //dp[j]含义：容量为j的背包所能背的最大价值为dp[j]

        //那么他的重量和价值是多少：他的重量和价值都是一样的
        //我们只需要判断dp[11] = 11就行了

        int sum = Arrays.stream(nums).sum();
        if(sum % 2 != 0){
            return false;
        }

        int target = sum / 2;

        System.out.println("  0  1  2  3");
        int[] dp = new int[target+1];
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= 0; j--) {
                if(j >= nums[i]){
                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }
            System.out.print(nums[i]);
            System.out.println(Arrays.toString(dp));
        }
        return dp[target] == target;
    }
}
